#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseBetween(ListNode* head, int m, int n) {
    if (head == nullptr || m >= n) {
        return head;
    }

    // 创建虚拟头节点，简化边界情况的处理
    ListNode* dummyHead = new ListNode(0);
    dummyHead->next = head;
    ListNode* pre = dummyHead;

    // 找到需要翻转部分的起始节点的前一个节点
    for (int i = 0; i < m - 1; i++) {
        pre = pre->next;
    }
    ListNode* start = pre->next;

    // 开始迭代翻转节点
    for (int i = 0; i < n - m; i++) {
        ListNode* temp = pre->next;
        pre->next = start->next;
        start->next = start->next->next;
        pre->next->next = temp;
    }

    // 调整翻转部分的起始节点和前一个节点的指针
    ListNode* result = dummyHead->next;
    delete dummyHead; // 释放虚拟头节点的内存
    return result;
}

int main() {
    // 创建测试链表
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    int m = 2, n = 4;
    ListNode* result = reverseBetween(head, m, n);

    // 输出翻转后的链表
    std::cout << "Updated list: ";
    while (result != nullptr) {
        std::cout << result->val << " ";
        result = result->next;
    }
    std::cout << std::endl;

    // 释放链表中剩余的节点的内存
    while (head != nullptr) {
        ListNode* toRemove = head;
        head = head->next;
        delete toRemove;
    }

    return 0;
}
